1028H - Make Square - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;



#define rep(i,l,r) for(register int i = l ; i <= r ; i++)

#define repd(i,r,l) for(register int i = r ; i >= l ; i--)

#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)

#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)

#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)

#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))

#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))

#define pb push_back

#define prev prev_

#define stack stack_

#define mp make_pair

#define fi first

#define se second

#define lowbit(x) (x&(-x))



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair<int,int> pr;



const int inf = 2e8;

const int N = 6e6 + 10;

const int maxn = 200020;



vector <pr> qry[maxn];

vector <int> vec;

int prime[N],tag[N],cnt,mn[N];

int id[N][8],a[maxn];

int n,q,ans[maxn * 10],rec[20];



void init(){

	rep(i,2,5040000){

		if ( !tag[i] ) prime[++cnt] = i , mn[i] = i;

		rep(j,1,cnt){

			if ( prime[j] * i > 5040000 ) break;

			tag[prime[j] * i] = 1;

			mn[prime[j] * i] = prime[j];

			if ( i % prime[j] == 0 ) break;

		}

	}

}

void factor(int x){

	vec.clear();

	while ( x > 1 ){

		int c = mn[x],cnt = 0;

		while ( x % c == 0 ) x /= c , cnt++;

		if ( cnt & 1 ) vec.pb(c);

	}	

}

void dfs(int n,int cur,int k,int pos){

	if ( n == vec.size() ){

		int c = vec.size();

		rep(i,k,7){

			if ( id[cur][i] ){

				rec[i + c - 2 * k] = max(rec[i + c - 2 * k],id[cur][i]);

			}

		}

		id[cur][c] = pos;

		return;

	}

	dfs(n + 1,cur * vec[n],k + 1,pos);

	dfs(n + 1,cur,k,pos);

}

void solve(){

	rep(i,1,n){

		factor(a[i]);

		dfs(0,1,0,i);

		rvc(j,qry[i]){

			rep(k,0,14){

				if ( qry[i][j].fi <= rec[k] ){ ans[qry[i][j].se] = k; break; }

			}

		}

	}

	rep(i,1,q) printf("%d\n",ans[i]);

}

int main(){

	init();

	scanf("%d %d",&n,&q);

	rep(i,1,n) scanf("%d",&a[i]);

	rep(i,1,q){

		int l,r;

		scanf("%d %d",&l,&r);

		qry[r].pb(mp(l,i));

	}

	solve();

}